package demo.practice.leetcode;

public class IsBalanced2 {


    public class TreeNode {
       public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public boolean isBalanced(TreeNode root) {

        boolean br = isBalancedThisNode(root);
        if (!br)
            return br;
        else {
            if (root.left != null) {
                br = br && isBalanced(root.left);
            }
            if (root.right != null) {
                br = br && isBalanced(root.right);
            }
            return br;
        }
    }

    /**
     * 单个节点是否是平衡的
     *
     * @param root
     * @return
     */
    public boolean isBalancedThisNode(TreeNode root) {
        if (root == null)
            return true;
        Integer rd = deep(root.right, null);
        Integer ld = deep(root.left, null);

        if (rd - ld > 1 || ld - rd > 1) {
            return false;
        } else {
            return true;
        }
    }


    /**
     * @param node
     * @param d
     * @return
     */
    public Integer deep(TreeNode node, Integer d) {
        if (d == null) {
            d = 0;
        }
        if (node == null)
            return d;
        Integer ld = deep(node.left, d++);
        Integer rd = deep(node.right, d++);
        return ld > rd ? ld : rd;
    }


}
